package Elementary_algorithm.String;

/*
给定一个字符串s，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1。

示例 1：

输入: s = "leetcode"
输出: 0
示例 2:

输入: s = "loveleetcode"
输出: 2
示例 3:

输入: s = "aabb"
输出: -1

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn5z8r/
 */

import org.junit.Test;

import java.util.*;

public class _03字符串中的第一个唯一字符 {


    @Test
    public void test() {

        System.out.println(firstUniqChar("aabb"));

    }

    //独立
    //使用哈希表存储索引
    //O(n)
    public int firstUniqChar(String s) {

        int index = Integer.MAX_VALUE;
        char[] charArray = s.toCharArray();
        HashMap<Character,Integer> hashMap = new HashMap<>();

        for (int i = 0; i < charArray.length; i++) {
            if(!hashMap.containsKey(charArray[i])){
                hashMap.put(charArray[i],i);
            }else {
                hashMap.put(charArray[i],-1);
            }
        }
        Collection<Integer> values = hashMap.values();
        for (Integer value : values) {
            if(value != -1){
                index = Math.min(value,index);
            }else {
                continue;
            }
        }
        return index == Integer.MAX_VALUE ? -1 : index;
    }

    //官解一:使用哈希表存储频数
     /*
    我们可以对字符串进行两次遍历。
    在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。
    在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 −1。
    */

    //更简洁，速度差不多
    //O(n)
    class Solution1 {
        public int firstUniqChar(String s) {
            Map<Character, Integer> frequency = new HashMap<Character, Integer>();
            for (int i = 0; i < s.length(); ++i) {
                char ch = s.charAt(i);
                frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
            }
            for (int i = 0; i < s.length(); ++i) {
                if (frequency.get(s.charAt(i)) == 1) {
                    return i;
                }
            }
            return -1;
        }
    }


    //官解三:队列

    /*
    我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。
    具体地，我们使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。
    当我们对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个二元组放入队尾，
    否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 −1）选择弹出队首的元素，
    直到队首元素「真的」只出现了一次或者队列为空。
    在遍历完成后，如果队列为空，说明没有不重复的字符，返回 −1，否则队首的元素即为第一个不重复的字符以及其索引的二元组。
    */

    //思路很有意思
    class Solution2 {
        public int firstUniqChar(String s) {
            Map<Character, Integer> position = new HashMap<Character, Integer>();
            Queue<Pair> queue = new LinkedList<Pair>();
            int n = s.length();
            for (int i = 0; i < n; ++i) {
                char ch = s.charAt(i);
                if (!position.containsKey(ch)) {
                    position.put(ch, i);
                    queue.offer(new Pair(ch, i));
                } else {
                    position.put(ch, -1);
                    while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
                        queue.poll();
                    }
                }
            }
            return queue.isEmpty() ? -1 : queue.poll().pos;
        }

        class Pair {
            char ch;
            int pos;

            Pair(char ch, int pos) {
                this.ch = ch;
                this.pos = pos;
            }
        }
    }

}
